package second.greedy;

import java.util.Arrays;

public class Solution09 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length && k > 0; i++) {
            if (nums[i] > 0) break;
            nums[i] = -nums[i];
            k--;
        }
        Arrays.sort(nums);
        if (k % 2 != 0) nums[0] = -nums[0];
        int res = 0;
        for (int x : nums) {
            res += x;
        }
        return res;
    }
}

